//#include <iostream>
//#include <vector>
//#include <queue>
//using namespace std;
//
//// struct ListNode {
////    int val;
////    ListNode* next;
////    ListNode() : val(0), next(nullptr) {}
////    ListNode(int x) : val(x), next(nullptr) {}
////    ListNode(int x, ListNode* next) : val(x), next(next) {}
////    
////};
//
//// class Solution {
//// public:
////     ListNode* swapPairs(ListNode* head) {
////         ListNode* newhead = new ListNode(0, head);
////
////         ListNode* prev = newhead;
////         ListNode* cur = head;
////         ListNode* next = cur == nullptr ? nullptr : cur->next;
////         ListNode* nnext = next == nullptr ? nullptr : next->next;
////
////         while (cur && next)
////         {
////             prev->next = next;
////             next->next = cur;
////             cur->next = nnext;
////
////             prev = cur;
////             cur = nnext;
////             next = cur == nullptr ? nullptr : cur->next;
////             nnext = next == nullptr ? nullptr : next->next;
////         }
////
////         return newhead->next;
////     }
//// };
////
////class Solution {
////public:
////
////    ListNode* Reverse(ListNode* head)
////    {
////        if (head->next == nullptr)
////            return head;
////
////        ListNode* next = head->next;
////        ListNode* ret = Reverse(head->next);
////        head->next = nullptr;
////        next->next = head;
////
////        return ret;
////    }
////
////    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
////        ListNode* nullhead = new ListNode();
////        int sum = 0;
////        int mod = 0;
////        while (l1 && l2)
////        {
////            sum = l1->val + l2->val + mod;
////
////            l1 = l1->next;
////            l2 = l2->next;
////
////            ListNode* newNode = new ListNode(sum % 10);
////            newNode->next = nullhead->next;
////            nullhead->next = newNode;
////
////            mod = sum / 10;
////        }
////
////        while (l1)
////        {
////            sum = mod + l1->val;
////
////            l1 = l1->next;
////
////            ListNode* newNode = new ListNode(sum % 10);
////            newNode->next = nullhead->next;
////            nullhead->next = newNode;
////
////            mod = sum / 10;
////        }
////
////        while (l2)
////        {
////            sum = mod + l2->val;
////
////            l2 = l2->next;
////
////            ListNode* newNode = new ListNode(sum % 10);
////            newNode->next = nullhead->next;
////            nullhead->next = newNode;
////
////            mod = sum / 10;
////        }
////        if (mod != 0)
////        {
////            ListNode* newNode = new ListNode(mod);
////            newNode->next = nullhead->next;
////            nullhead->next = newNode;
////        }
////
////        ListNode* ret = Reverse(nullhead->next);
////
////        return ret;
////    }
////};
////
////class Solution {
////public:
////    ListNode* swapPairs(ListNode* head) {
////        if (head == nullptr || head->next == nullptr)
////            return head;
////
////        ListNode* next = head->next;
////        ListNode* ret = swapPairs(next->next);
////
////        next->next = head;
////        head->next = ret;
////
////        return next;
////    }
////};
////
////
////class Solution {
////public:
////
////    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
////        if ((!a) || (!b)) return a ? a : b;
////        ListNode head, * tail = &head, * aPtr = a, * bPtr = b;
////        while (aPtr && bPtr) {
////            if (aPtr->val < bPtr->val) {
////                tail->next = aPtr; aPtr = aPtr->next;
////            }
////            else {
////                tail->next = bPtr; bPtr = bPtr->next;
////            }
////            tail = tail->next;
////        }
////        tail->next = (aPtr ? aPtr : bPtr);
////        return head.next;
////    }
////
////
////    ListNode* _mergeKlists(int begin, int end, vector<ListNode*>& lists)
////    {
////        if (begin == end)
////            return lists[begin];
////
////        if (begin > end) return nullptr;
////
////        int mid = (begin + end) / 2;
////        ListNode* l1 = _mergeKlists(begin, mid, lists);
////        ListNode* l2 = _mergeKlists(mid + 1, end, lists);
////
////        return mergeTwoLists(l1, l2);
////    }
////
////    ListNode* mergeKLists(vector<ListNode*>& lists) {
////        return _mergeKlists(0, lists.size() - 1, lists);
////    }
////};
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//
//
////class Solution {
////public:
////
////    class Great
////    {
////    public:
////        bool operator()(ListNode* node1, ListNode* node2)
////        {
////            return node1->val > node2->val;
////        }
////
////    };
////
////    ListNode* mergeKLists(vector<ListNode*>& lists) {
////        priority_queue<ListNode*, vector<ListNode*>, Great> pq;
////        ListNode* newhead = new ListNode(0, nullptr);
////        ListNode* tail = newhead;
////
////        for (auto e : lists)
////        {
////            if (e)
////                pq.push(e);
////        }
////
////        while (!pq.empty())
////        {
////            ListNode* next = pq.top()->next;
////
////            tail->next = pq.top();
////            tail = tail->next;
////            pq.pop();
////            if (next)
////                pq.push(next);
////        }
////
////        tail = newhead->next;
////        delete newhead;
////        return tail;
////    }
////};
////
////class Solution {
////public:
////
////    int CountListNum(ListNode* head)
////    {
////        ListNode* cur = head;
////        int ret = 0;
////        while (cur)
////        {
////            cur = cur->next;
////            ret++;
////        }
////        return ret;
////    }
////
////    ListNode* reverseKGroup(ListNode* head, int k) {
////
////        int n = CountListNum(head);
////        n = n / k;
////
////        ListNode* newhead = new ListNode(0);
////        ListNode* ret = newhead, * cur = head, * next = head->next;
////
////        for (int i = 0; i < n; i++)
////        {
////            ListNode* prev = cur;
////            for (int j = 0; j < k; j++)
////            {
////                cur->next = newhead->next;
////                newhead->next = cur;
////
////                cur = next;
////                if (next)
////                    next = next->next;
////                else break;
////            }
////            newhead = prev;
////        }
////
////        newhead->next = cur;
////
////        cur = ret->next;
////        delete ret;
////
////        return cur;
////    }
////};
////
////class Solution {
////public:
////    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
////        ListNode* l1 = headA, * l2 = headB;
////
////        while (l1 != l2)
////        {
////            l1 = l1 ? l1->next : headB;
////            l2 = l2 ? l2->next : headA;
////        }
////
////        return l1;
////    }
////};
//
////class Solution {
////public:
////    ListNode* reverseList(ListNode* head) {
////        ListNode* nullnode = new ListNode(0);
////        ListNode* cur = head;
////        while (cur)
////        {
////            ListNode* next = cur->next;
////            cur->next = nullnode->next;
////            nullnode->next = cur;
////            cur = next;
////        }
////        cur = nullnode->next;
////        delete nullnode;
////        return cur;
////    }
////};
////
////class Solution {
////public:
////    ListNode* reverseList(ListNode* head) {
////        ListNode* nullnode = new ListNode(0);
////        ListNode* cur = head;
////        while (cur)
////        {
////            ListNode* next = cur->next;
////            cur->next = nullnode->next;
////            nullnode->next = cur;
////            cur = next;
////        }
////        cur = nullnode->next;
////        delete nullnode;
////        return cur;
////    }
////
////    bool isPalindrome(ListNode* head) {
////        ListNode* nullnode = new ListNode(0);
////        ListNode* fast = nullnode, * slow = nullnode;
////        nullnode->next = head;
////        while (fast->next && fast->next->next)
////        {
////            fast = fast->next->next;
////            slow = slow->next;
////        }
////
////        slow = slow->next;
////        slow = reverseList(slow);
////
////        while (slow)
////        {
////            if (head->val != slow->val)
////                return false;
////            head = head->next;
////            slow = slow->next;
////        }
////
////        return true;
////    }
////};  
////
////class Solution {
////public:
////    bool hasCycle(ListNode* head) {
////        ListNode* nullnode = new ListNode(0);
////        nullnode->next = head;
////        ListNode* fast = nullnode, * slow = nullnode;
////        while (fast->next && fast->next->next)
////        {
////            fast = fast->next->next;
////            slow = slow->next;
////            if (slow == fast)
////            {
////                delete nullnode;
////                return true;
////            }
////        }
////
////        delete nullnode;
////        return false;
////    }
////};
////
////class Solution {
////public:
////    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB, ListNode* tail) {
////        ListNode* l1 = headA, * l2 = headB;
////
////        while (l1 != l2)
////        {
////            l1 = l1 != tail ? l1->next : headB;
////            l2 = l2 != tail ? l2->next : headA;
////        }
////
////        return l1;
////    }
////
////    ListNode* detectCycle(ListNode* head) {
////        ListNode* nullnode = new ListNode(0);
////        nullnode->next = head;
////        ListNode* fast = nullnode, * slow = nullnode;
////        while (fast->next && fast->next->next)
////        {
////            fast = fast->next->next;
////            slow = slow->next;
////            if (slow == fast)
////            {
////                return getIntersectionNode(head, slow->next, slow);
////            }
////        }
////
////        delete nullnode;
////        return nullptr;
////    }
////
////};
////
////class Solution {
////public:
////    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
////        ListNode* nullnode = new ListNode(0);
////        ListNode* tail = nullnode;
////        ListNode* cur1 = list1, * cur2 = list2;
////        while (cur1 && cur2)
////        {
////            if (cur1->val <= cur2->val)
////            {
////                ListNode* next = cur1->next;
////                tail->next = cur1;
////                tail = tail->next;
////                cur1 = next;
////            }
////            else
////            {
////                ListNode* next = cur2->next;
////                tail->next = cur2;
////                tail = tail->next;
////                cur2 = next;
////            }
////        }
////
////        while (cur1)
////        {
////            ListNode* next = cur1->next;
////            tail->next = cur1;
////            tail = tail->next;
////            cur1 = next;
////        }
////
////        while (cur2)
////        {
////            ListNode* next = cur2->next;
////            tail->next = cur2;
////            tail = tail->next;
////            cur2 = next;
////        }
////
////        cur1 = nullnode->next;
////        delete nullnode;
////        return cur1;
////    }
////};
////
////class Solution {
////public:
////    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
////        ListNode* nullnode = new ListNode(0);
////        ListNode* tail = nullnode;
////        ListNode* cur1 = l1, * cur2 = l2;
////
////        int mod = 0;
////        while (cur1 && cur2)
////        {
////            int sum = cur1->val + cur2->val + mod;
////            tail->next = new ListNode(sum % 10);
////            tail = tail->next;
////            mod = sum / 10;
////
////            cur1 = cur1->next;
////            cur2 = cur2->next;
////        }
////
////        while (cur1)
////        {
////            int sum = cur1->val + mod;
////            tail->next = new ListNode(sum % 10);
////            tail = tail->next;
////            mod = sum / 10;
////
////            cur1 = cur1->next;
////        }
////
////        while (cur2)
////        {
////            int sum = cur2->val + mod;
////            tail->next = new ListNode(sum % 10);
////            tail = tail->next;
////            mod = sum / 10;
////
////            cur2 = cur2->next;
////        }
////
////        if (mod)
////        {
////            tail->next = new ListNode(mod);
////        }
////
////        cur1 = nullnode->next;
////        delete nullnode;
////        return cur1;
////    }
////};
////
////class Solution {
////public:
////    ListNode* removeNthFromEnd(ListNode* head, int n) {
////        ListNode* nullnode = new ListNode(0);
////        nullnode->next = head;
////        ListNode* tail = nullnode;
////        n++;
////        while (tail && n--)
////        {
////            tail = tail->next;
////        }
////
////        ListNode* cur = nullnode;
////        while (tail)
////        {
////            tail = tail->next;
////            cur = cur->next;
////        }
////
////        cur->next = cur->next->next;
////        tail = nullnode->next;
////        delete nullnode;
////        return tail;
////    }
////};
////
////class Solution {
////public:
////    ListNode* swapPairs(ListNode* head) {
////        ListNode* nullnode = new ListNode(0);
////        nullnode->next = head;
////        ListNode* pprev = nullnode, * prev, * cur, * next;
////        if (head)
////            prev = head;
////        else
////        {
////            delete nullnode;
////            return head;
////        }
////
////        if (prev->next)
////            cur = prev->next;
////        else
////        {
////            delete nullnode;
////            return head;
////        }
////
////        if (cur)
////            next = cur->next;
////        else
////        {
////            delete nullnode;
////            return head;
////        }
////
////        while (cur)
////        {
////            pprev->next = cur;
////            cur->next = prev;
////            prev->next = next;
////
////            pprev = prev;
////            if (next)
////                prev = next;
////            else break;
////
////            if (prev->next)
////                cur = prev->next;
////            else break;
////            next = cur->next;
////        }
////
////        cur = nullnode->next;
////        delete nullnode;
////        return cur;
////    }
////};
////
/////**
//// * Definition for singly-linked list.
//// * struct ListNode {
//// *     int val;
//// *     ListNode *next;
//// *     ListNode() : val(0), next(nullptr) {}
//// *     ListNode(int x) : val(x), next(nullptr) {}
//// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
//// * };
//// */
////class Solution {
////public:
////    ListNode* reverseKGroup(ListNode* head, int k) {
////        int n = 0;
////        ListNode* cur = head;
////        while (cur)
////        {
////            cur = cur->next;
////            n++;
////        }
////
////        n /= k;
////
////        ListNode* nullnode = new ListNode(0);
////        nullnode->next = head;
////        cur = head;
////        ListNode* next = head;
////
////        ListNode* tail = nullnode;
////
////        for (int j = 0; j < n; j++)
////        {
////            ListNode* prev = cur;
////            for (int i = 0; cur && i < k; i++)
////            {
////                next = cur->next;
////                cur->next = tail->next;
////                tail->next = cur;
////                cur = next;
////            }
////            tail = prev;
////        }
////
////        tail->next = next;
////        cur = nullnode->next;
////        delete nullnode;
////        return cur;
////    }
////};
////
////
////// Definition for a Node.
////class Node {
////public:
////    int val;
////    Node* next;
////    Node* random;
////
////    Node(int _val) {
////        val = _val;
////        next = NULL;
////        random = NULL;
////    }
////};
////
////
////class Solution {
////public:
////    Node* copyRandomList(Node* head) {
////        Node* cur = head;
////        Node* ret = nullptr;
////        while (cur)
////        {
////            Node* node = new Node(cur->val);
////            if (cur == head)
////                ret = node;
////            node->next = cur->next;
////            cur->next = node;
////            cur = cur->next->next;
////        }
////
////        cur = head;
////        while (cur)
////        {
////            Node* Newnode = cur->next;
////            Node* next = Newnode->next;
////            Newnode->random = cur->random ? cur->random->next : nullptr;
////            cur = next;
////        }
////
////        cur = head;
////        while (cur)
////        {
////            Node* Newnode = cur->next;
////            Node* next = Newnode->next;
////            cur->next = next;
////            Newnode->next = next ? next->next : nullptr;
////            cur = next;
////        }
////        return ret;
////    }
////};
//
////class Solution {
////public:
////
////    class Less
////    {
////    public:
////        bool operator()(ListNode* l1, ListNode* l2)
////        {
////            return l1->val > l2->val;
////        }
////    };
////
////    ListNode* sortList(ListNode* head) {
////        priority_queue<ListNode*, vector<ListNode*>, Less> heap;
////
////        ListNode* cur = head;
////        while (cur)
////        {
////            heap.push(cur);
////            cur = cur->next;
////        }
////
////        ListNode* nullnode = new ListNode(0), * tail = nullnode;
////        while (!heap.empty())
////        {
////            ListNode* node = heap.top();
////            heap.pop();
////            node->next = tail->next;
////            tail->next = node;
////            tail = node;
////        }
////
////        cur = nullnode->next;
////        delete nullnode;
////        return cur;
////    }
////};
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
////class Solution {
////public:
////    class Less
////    {
////    public:
////        bool operator()(ListNode* l1, ListNode* l2)
////        {
////            return l1->val > l2->val;
////        }
////    };
////
////    ListNode* mergeKLists(vector<ListNode*>& lists) {
////        priority_queue<ListNode*, vector<ListNode*>, Less> heap;
////        for (auto e : lists)
////        {
////            if (e)
////                heap.push(e);
////        }
////
////        ListNode* nullnode = new ListNode(0), * tail = nullnode;
////        while (!heap.empty())
////        {
////            ListNode* node = heap.top();
////            heap.pop();
////            if (node->next)
////                heap.push(node->next);
////
////            node->next = tail->next;
////            tail->next = node;
////            tail = node;
////        }
////
////        tail = nullnode->next;
////        delete nullnode;
////        return tail;
////    }
////};
//
//#include <unordered_map>
//
////class LRUCache {
////    struct ListNode
////    {
////        ListNode(int val, int key) : _val(val), _key(key), _prev(nullptr), _next(nullptr)
////        {}
////
////        int _key;
////        int _val;
////        ListNode* _prev;
////        ListNode* _next;
////    };
////
////    struct DoubleLinkedList
////    {
////        DoubleLinkedList()
////        {
////            _nullhead = new ListNode(-1, -1);
////            _nullhead->_prev = _nullhead;
////            _nullhead->_next = _nullhead;
////        }
////
////        void Push(ListNode* newnode)
////        {
////            ListNode* next = _nullhead->_next;
////
////            newnode->_next = next;
////            newnode->_prev = _nullhead;
////            _nullhead->_next = newnode;
////            next->_prev = newnode;
////
////        }
////
////        void Modify(ListNode* node)
////        {
////            ListNode* prev = node->_prev;
////            ListNode* next = node->_next;
////
////            prev->_next = next;
////            next->_prev = prev;
////
////            Push(node);
////        }
////
////        void Pop_Back()
////        {
////            ListNode* node = _nullhead->_prev;
////            ListNode* prev = node->_prev;
////            ListNode* next = node->_next;
////            if(prev != _nullhead)
////            {
////                prev->_next = next;
////                next->_prev = prev;
////                
////                delete node;
////            }
////        }
////
////        ListNode* _nullhead;
////    };
////
////    unordered_map<int, ListNode*> hash;
////    DoubleLinkedList _dlist;
////    int n;
////    int _capacity;
////public:
////    LRUCache(int capacity)
////    {
////        n = 0;
////        _capacity = capacity;
////    }
////
////    int get(int key)
////    {
////        if (hash.count(key))
////        {
////            _dlist.Modify(hash[key]);
////            return hash[key]->_val;
////        }
////        else
////            return -1;
////    }
////
////    void put(int key, int value)
////    {
////        if (hash.count(key))
////        {
////            hash[key]->_val = value;
////            _dlist.Modify(hash[key]);
////        }
////        else
////        {
////            ListNode* newnode = new ListNode(value, key);
////            hash[key] = newnode;
////            _dlist.Push(newnode);
////            n++;
////            if (n > _capacity)
////            {
////                int k = _dlist._nullhead->_prev->_key;
////                _dlist.Pop_Back();
////                hash.erase(k);
////            }
////        }
////    }
////};
//
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//
//struct ListNode {
//    int val;
//    ListNode* next;
//    ListNode() : val(0), next(nullptr) {}
//    ListNode(int x) : val(x), next(nullptr) {}
//    ListNode(int x, ListNode* next) : val(x), next(next) {}
//};
//
//class Solution {
//public:
//    ListNode* deleteDuplicates(ListNode* head)
//    {
//        if (head == nullptr) return head;
//
//
//        ListNode* nullnode = new ListNode(-1);
//        ListNode* cur = nullnode;
//        ListNode* l = head, * r = head;
//        while (r)
//        {
//            int count = 0;
//            while (r && l->val == r->val)
//            {
//                r = r->next;
//                count++;
//            }
//            if (count > 1)
//            {
//                while (l != r)
//                {
//                    ListNode* next = l->next;
//                    delete l;
//                    l = next;
//                }
//                cur->next = nullptr;
//            }
//            else
//            {
//                cur->next = l;
//                cur = cur->next;
//                l = l->next;
//            }
//        }
//        l = nullnode->next;
//        delete nullnode;
//        return l;
//    }
//};
//
//int main()
//{
//    //vector<string> com = { "LRUCache","put","put","get","put","get","put","get","get","get" };
//   /* LRUCache l(2);
//    cout << "null ";
//
//    l.put(1, 0);
//    cout << "null ";
//
//    l.put(2, 2);
//    cout << "null ";
//    
//    
//    cout << l.get(1) << " ";
//
//    l.put(3, 3);
//    cout << "null ";
//    
//    cout << l.get(2) << " ";
//
//    l.put(4, 4);
//    cout << "null ";
//
//    cout << l.get(1) << " ";
//    cout << l.get(3) << " ";
//    cout << l.get(4) << " ";*/
//
//    //vector<ListNode*> lists = 1, 4, 5, 1, 3, 4, 2, 6
//    return 0;
//}
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode(int x) : val(x), next(NULL) {}
// * };
// */
//class Solution {
//public:
//    ListNode* detectCycle(ListNode* head)
//    {
//        ListNode* slow = head, * fast = head;
//        while (slow && fast && fast->next)
//        {
//            slow = slow->next;
//            fast = fast->next->next;
//            if (slow == fast)
//            {
//                ListNode* end = fast;
//                slow = head;
//                fast = fast->next;
//                while (slow != fast)
//                {
//                    slow = slow->next;
//                    fast = fast == end ? head : fast->next;
//                }
//
//                return slow;
//            }
//        }
//
//        return nullptr;
//    }
//};
//
//class Solution {
//public:
//
//    class Less
//    {
//    public:
//        bool operator()(ListNode* l1, ListNode* l2)
//        {
//            return l1->val > l2->val;
//        }
//    };
//
//    ListNode* sortList(ListNode* head) {
//        priority_queue<ListNode*, vector<ListNode*>, Less> heap;
//
//        ListNode* cur = head;
//        while (cur)
//        {
//            heap.push(cur);
//            cur = cur->next;
//        }
//
//        ListNode* nullnode = new ListNode(0), * tail = nullnode;
//        while (!heap.empty())
//        {
//            ListNode* node = heap.top();
//            heap.pop();
//            node->next = tail->next;
//            tail->next = node;
//            tail = node;
//        }
//
//        cur = nullnode->next;
//        delete nullnode;
//        return cur;
//    }
//};
//
///*
//// Definition for a Node.
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    Node(int _val) {
//        val = _val;
//        next = NULL;
//        random = NULL;
//    }
//};
//*/
//
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    Node(int _val) {
//        val = _val;
//        next = NULL;
//        random = NULL;
//    }
//};
//
//class Solution {
//public:
//    Node* copyRandomList(Node* head)
//    {
//        if (head == nullptr)
//            return head;
//
//        Node* cur = head;
//        while (cur)
//        {
//            Node* next = cur->next;
//            Node* newnode = new Node(cur->val);
//            newnode->next = next;
//            cur->next = newnode;
//
//            cur = next;
//        }
//
//        cur = head;
//        while (cur)
//        {
//            cur->next->random = cur->random ? cur->random->next : nullptr;
//            cur = cur->next->next;
//        }
//
//        Node* nullnode = new Node(-1), * tail = nullnode;
//        cur = head;
//        while (cur)
//        {
//            Node* next = cur->next->next;
//
//            cur->next->next = tail->next;
//            tail->next = cur->next;
//            tail = tail->next;
//
//            cur->next = next;
//            cur = next;
//        }
//
//        cur = nullnode->next;
//        delete nullnode;
//        return cur;
//    }
//};
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//public:
//    ListNode* swapPairs(ListNode* head)
//    {
//        if (head == nullptr || head->next == nullptr)
//            return head;
//
//        ListNode* ret = head->next;
//        ListNode* cur = head;
//        while (cur && cur->next)
//        {
//            ListNode* next = cur->next->next;
//
//            cur->next->next = cur;
//            if (next == nullptr || next->next == nullptr)
//                cur->next = next;
//            else cur->next = next->next;
//
//            cur = next;
//        }
//
//        return ret;
//    }
//};
//
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//public:
//    ListNode* reverseKGroup(ListNode* head, int k)
//    {
//        int n = 0;
//        ListNode* cur = head;
//        while (cur)
//        {
//            n++;
//            cur = cur->next;
//        }
//
//        cur = head;
//        ListNode* nullnode = new ListNode(-1);
//        ListNode* prev = nullnode, * tail = nullnode, * next = nullptr;
//        int i = 1;
//        while (i <= n)
//        {
//            if (n - i + 1 >= k)
//            {
//                for (int j = 0; j < k; j++, i++)
//                {
//                    next = cur->next;
//                    cur->next = prev->next;
//                    prev->next = cur;
//                    if (tail == prev)
//                        tail = cur;
//
//                    cur = next;
//                }
//                prev = tail;
//            }
//            else
//            {
//                prev->next = cur;
//                break;
//            }
//        }
//
//        cur = nullnode->next;
//        delete nullnode;
//        return cur;
//    }
//};

#include <iostream>
using namespace std;

struct ListNode 
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x = 0) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode* nullnode = new ListNode(0);
    ListNode* cur = head;
    while (cur)
    {
        ListNode* next = cur->next;
        cur->next = nullnode->next;
        nullnode->next = cur;
        cur = next;
    }
    cur = nullnode->next;
    delete nullnode;
    return cur;
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{
    ListNode* nullhead = new ListNode(-1);
    ListNode* tail = nullhead;
    ListNode* l = list1, * r = list2;
    while (l && r)
    {
        if (l->val >= r->val)
        {
            tail->next = r;
            r = r->next;
        }
        else
        {
            tail->next = l;
            l = l->next;
        }
        tail = tail->next;
    }

    while (l)
    {
        tail->next = l;
        l = l->next;
        tail = tail->next;
    }

    while (r)
    {
        tail->next = r;
        r = r->next;
        tail = tail->next;
    }

    l = nullhead->next;
    delete nullhead;
    return l;
}

ListNode* func(ListNode* node1, ListNode* node2)
{
    return reverseList(mergeTwoLists(node1, node2));
}

int main()
{
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(3);
    ListNode* node3 = new ListNode(5);
    node1->next = node2;
    node2->next = node3;

    ListNode* node4 = new ListNode(2);
    ListNode* node5 = new ListNode(4);
    ListNode* node6 = new ListNode(7);
    node4->next = node5;
    node5->next = node6;

    ListNode* ret =  func(node1, node4);

    while (ret)
    {
        cout << ret->val << " ";
        ret = ret->next;
    }
    cout << endl;

    return 0;
}

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int slow = 0, fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while (slow != fast)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }


        return slow;
    }
};